package com.cat.dataStructure03;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/count-subarrays-with-fixed-bounds/
 * @create 2025/11/13 11:18
 * @since JDK17
 */

public class Solution53 {
    int h1, h2, t1, t2;
    public long countSubarrays(int[] nums, int minK, int maxK) {
        long ans = 0;
        int n = nums.length;
        int[] min = new int[n], max = new int[n];
        for (int l = 0, r = 0; r < n; r++) {
            while (h1 < t1 && nums[min[t1 - 1]] >= nums[r]) {  // 最小
                t1--;
            }
            while (h2 < t2 && nums[max[t2 - 1]] <= nums[r]) {    // 最大
                t2--;
            }
            min[t1++] = max[t2++] = r;
            if (nums[min[h1]] < minK || nums[max[h2]] > maxK) { // 清空队列
                l = r + 1;
                t1 = h1;
                t2 = h2;
            }
            if (nums[min[h1]] == minK && nums[max[h2]] == maxK) {   // 统计答案
                int left = Math.min(min[h1], max[h2]) - l + 1;
                ans += left;
            }
        }

        return ans;
    }
}
